In mathematics, a discrete Fourier transform (DFT) transforms one function from a time domain representation to a frequency domain representation. The DFT requires an input function that is discrete. Such inputs are often created by sampling a continuous function, such as an amplitude of sound over time. The discrete input function must have a limited duration, such as one period of a periodic sequence or a windowed segment of a longer sequence. The input to the DFT is a finite sequence of real or complex numbers, making the DFT ideal for processing information stored in computers. In particular, the DFT is widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal to solve partial differential equations, and to perform other operations such as convolutions or multiplying large integers. A key enabling factor for these applications is the fact that the DFT can be computed efficiently in practice using a fast Fourier transform (FFT) algorithm.
Target devices such as field programmable gate arrays (FPGAs), structured application specific integrated circuits (ASICs), and ASICs are used to implement large systems that may include million of gates and megabits of embedded memory. The target devices often have resources available to create DFT engines to perform DFT operations. When designing a system on the target device, a designer is limited by the tools of an electronic design automation (EDA) tool and do not have an option for parameterization of DFT engines. In order to scale performance, the designer is required to design a DFT unit manually and use trial and error to determine whether sufficient throughput exists and whether resources on the target device have been efficiently allocated. This phase of the design often required additional time and resources.